#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int knightDialer(int n) {
        const int mod = 1e9 + 7;
        long long a = 1, b = 1, c = 1, d = 1;
        long long res = 10;
        for (int i = 0; i < n - 1; i++) {
            a %= mod; b %= mod; c %= mod; d %= mod;
            res = (4 * a + 2 * c + d) * 2 + b * 2 * 3;
            long long aa = a, bb = b, cc = c, dd = d;
            a = bb + cc;
            b = 2 * aa + dd;
            c = 2 * aa;
            d = 2 * bb;
        }
        return res % mod;
    }
};
int main()
{
	return 0;
}